# 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
# 满足 i != j、i != k 且 j != k
# 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
#
# 注意：答案中不可以包含重复的三元组。
#
#  示例 1：
# 输入：nums = [-1,0,1,2,-1,-4]
# 输出：[[-1,-1,2],[-1,0,1]]
# 解释：
# nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
# nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
# nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
# 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
# 注意，输出的顺序和三元组的顺序并不重要。
#
#  示例 2：
# 输入：nums = [0,1,1]
# 输出：[]
# 解释：唯一可能的三元组和不为 0
#
#  示例 3：
# 输入：nums = [0,0,0]
# 输出：[[0,0,0]]
# 解释：唯一可能的三元组和为 0 。
from typing import List


class Solution:
    """
        哈希表解法
        key 为 nums[i] value 为 i
    """

    def twoSum2(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i, num in enumerate(nums):
            if target - num in hashmap:
                return [hashmap[target - num], i]
            hashmap[num] = i
        return []

    """
    先排序（带上下标），然后转化成leetcode1 使用双指针解法即可
    """

    def twoSum1(self, nums: List[int], target: int) -> List[int]:
        newNums = sorted([(num, i) for i, num in enumerate(nums)], key=lambda x: x[0])
        i, j = 0, len(newNums) - 1
        while i < j:
            if newNums[i][0] + newNums[j][0] == target:
                return [newNums[i][1], newNums[j][1]]
            elif newNums[i][0] + newNums[j][0] < target:
                i += 1
            else:
                j -= 1
        return []

    """
    要满足
    nums[i] + nums[j] + nums[k] = 0 那么 nums[i] = -(nums[j] + nums[k])
    那么就可以转化成遍历数组，每次在数组的后面子段寻找两个数，满足 nums[i] = -(nums[j] + nums[k])
    就可以调用 leetcode167 的双指针解法
    """

    def threeSum(self, nums: List[int]) -> list[tuple[int, int, int]]:
        nums.sort()
        res = list[tuple[int, int, int]]()
        for i, num in enumerate(nums):
            # 重复的数不用计算
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 当前数据已经大于 0 的也可以跳过，因为经过排序后，后面b不可能还有满足 nums[i] = -(nums[j] + nums[k]) 的 j,k了
            if nums[i] > 0:
                break
            for tuple2 in self.twoSum(nums, i + 1, -num):
                res.append((num, tuple2[0], tuple2[1]))
        return res

    """
    返回从 start 下标开始的子数组中满足两个数和为 target 的所有数
    """

    def twoSum(self, nums: List[int], start: int, target: int) -> list[tuple[int, int]]:
        res = list[tuple[int, int]]()
        low, high = start, len(nums) - 1
        while low < high:
            # 避免重复计算
            if low > start and nums[low] == nums[low - 1]:
                low += 1
                continue
            if high < len(nums) - 1 and nums[high] == nums[high + 1]:
                high -= 1
                continue
            total = nums[low] + nums[high]
            if total == target:
                res.append((nums[low], nums[high]))
                low += 1
                high -= 1
            elif total < target:
                low += 1
            else:
                high -= 1
        return res


if __name__ == "__main__":
    nums = [-1, 0, 1, 2, -1, -4]
    # nums = [-2, 0, 0, 2, 2]
    print(Solution().threeSum(nums))
